Using Dominators for Solving Constrained Path Problems
Identifieur interne : 001949 ( Main/Exploration ); précédent : 001948; suivant : 001950Using Dominators for Solving Constrained Path Problems
Auteurs : Luis Quesada [Belgique] ; Peter Van Roy [Belgique] ; Yves Deville [Belgique] ; Raphaël Collet [Belgique]Source :
- Lecture Notes in Computer Science [ 0302-9743 ] ; 2006.
Abstract
Abstract: Constrained path problems have to do with finding paths in graphs subject to constraints. We present a constraint programming approach for solving the Ordered disjoint-paths problem (ODP), i.e., the Disjoint-paths problem where the pairs are associated with ordering constraints. In our approach, we reduce ODP to the Ordered simple path with mandatory nodes problem (OSPMN), i.e., the problem of finding a simple path containing a set of mandatory nodes in a given order. The reduction of the problem is motivated by the fact that we have an appropriate way of dealing with OSPMN based on DomReachability, a propagator that implements a generalized reachability constraint on a directed graph based on the concept of graph variables. The DomReachability constraint has three arguments: (1) a flow graph, i.e., a directed graph with a source node; (2) the dominance relation graph on nodes and edges of the flow graph; and (3) the transitive closure of the flow graph. Our experimental evaluation of DomReachability shows that it provides strong pruning, obtaining solutions with very little search. Furthermore, we show that DomReachability is also useful for defining a good labeling strategy. These experimental results give evidence that DomReachability is a useful primitive for solving constrained path problems over directed graphs.
Url:
DOI: 10.1007/11603023_6
Affiliations:
- Belgique
- Province du Brabant wallon, Région wallonne
- Louvain-la-Neuve
- Université catholique de Louvain
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 000533
- to stream Istex, to step Curation: 000419
- to stream Istex, to step Checkpoint: 001280
- to stream Main, to step Merge: 001977
- to stream Main, to step Curation: 001949
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Using Dominators for Solving Constrained Path Problems</title>
<author><name sortKey="Quesada, Luis" sort="Quesada, Luis" uniqKey="Quesada L" first="Luis" last="Quesada">Luis Quesada</name>
</author>
<author><name sortKey="Van Roy, Peter" sort="Van Roy, Peter" uniqKey="Van Roy P" first="Peter" last="Van Roy">Peter Van Roy</name>
</author>
<author><name sortKey="Deville, Yves" sort="Deville, Yves" uniqKey="Deville Y" first="Yves" last="Deville">Yves Deville</name>
</author>
<author><name sortKey="Collet, Raphael" sort="Collet, Raphael" uniqKey="Collet R" first="Raphaël" last="Collet">Raphaël Collet</name>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">ISTEX</idno>
<idno type="RBID">ISTEX:2BD8576A6CA4FBEB76BD8024838A23403B19C579</idno>
<date when="2005" year="2005">2005</date>
<idno type="doi">10.1007/11603023_6</idno>
<idno type="url">https://api.istex.fr/document/2BD8576A6CA4FBEB76BD8024838A23403B19C579/fulltext/pdf</idno>
<idno type="wicri:Area/Istex/Corpus">000533</idno>
<idno type="wicri:Area/Istex/Curation">000419</idno>
<idno type="wicri:Area/Istex/Checkpoint">001280</idno>
<idno type="wicri:doubleKey">0302-9743:2005:Quesada L:using:dominators:for</idno>
<idno type="wicri:Area/Main/Merge">001977</idno>
<idno type="wicri:Area/Main/Curation">001949</idno>
<idno type="wicri:Area/Main/Exploration">001949</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Using Dominators for Solving Constrained Path Problems</title>
<author><name sortKey="Quesada, Luis" sort="Quesada, Luis" uniqKey="Quesada L" first="Luis" last="Quesada">Luis Quesada</name>
<affiliation wicri:level="4"><country xml:lang="fr">Belgique</country>
<wicri:regionArea>Université catholique de Louvain, Place Sainte Barbe, 2, B-1348, Louvain-la-Neuve</wicri:regionArea>
<orgName type="university">Université catholique de Louvain</orgName>
<placeName><settlement type="city">Louvain-la-Neuve</settlement>
<region type="region" nuts="1">Région wallonne</region>
<region type="province" nuts="1">Province du Brabant wallon</region>
</placeName>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">Belgique</country>
</affiliation>
</author>
<author><name sortKey="Van Roy, Peter" sort="Van Roy, Peter" uniqKey="Van Roy P" first="Peter" last="Van Roy">Peter Van Roy</name>
<affiliation wicri:level="4"><country xml:lang="fr">Belgique</country>
<wicri:regionArea>Université catholique de Louvain, Place Sainte Barbe, 2, B-1348, Louvain-la-Neuve</wicri:regionArea>
<orgName type="university">Université catholique de Louvain</orgName>
<placeName><settlement type="city">Louvain-la-Neuve</settlement>
<region type="region" nuts="1">Région wallonne</region>
<region type="province" nuts="1">Province du Brabant wallon</region>
</placeName>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">Belgique</country>
</affiliation>
</author>
<author><name sortKey="Deville, Yves" sort="Deville, Yves" uniqKey="Deville Y" first="Yves" last="Deville">Yves Deville</name>
<affiliation wicri:level="4"><country xml:lang="fr">Belgique</country>
<wicri:regionArea>Université catholique de Louvain, Place Sainte Barbe, 2, B-1348, Louvain-la-Neuve</wicri:regionArea>
<orgName type="university">Université catholique de Louvain</orgName>
<placeName><settlement type="city">Louvain-la-Neuve</settlement>
<region type="region" nuts="1">Région wallonne</region>
<region type="province" nuts="1">Province du Brabant wallon</region>
</placeName>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">Belgique</country>
</affiliation>
</author>
<author><name sortKey="Collet, Raphael" sort="Collet, Raphael" uniqKey="Collet R" first="Raphaël" last="Collet">Raphaël Collet</name>
<affiliation wicri:level="4"><country xml:lang="fr">Belgique</country>
<wicri:regionArea>Université catholique de Louvain, Place Sainte Barbe, 2, B-1348, Louvain-la-Neuve</wicri:regionArea>
<orgName type="university">Université catholique de Louvain</orgName>
<placeName><settlement type="city">Louvain-la-Neuve</settlement>
<region type="region" nuts="1">Région wallonne</region>
<region type="province" nuts="1">Province du Brabant wallon</region>
</placeName>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">Belgique</country>
</affiliation>
</author>
</analytic>
<monogr></monogr>
<series><title level="s">Lecture Notes in Computer Science</title>
<imprint><date>2006</date>
</imprint>
<idno type="ISSN">0302-9743</idno>
<idno type="eISSN">1611-3349</idno>
</series>
<idno type="istex">2BD8576A6CA4FBEB76BD8024838A23403B19C579</idno>
<idno type="DOI">10.1007/11603023_6</idno>
<idno type="ChapterID">Chap6</idno>
<idno type="ChapterID">6</idno>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><textClass></textClass>
<langUsage><language ident="en">en</language>
</langUsage>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">Abstract: Constrained path problems have to do with finding paths in graphs subject to constraints. We present a constraint programming approach for solving the Ordered disjoint-paths problem (ODP), i.e., the Disjoint-paths problem where the pairs are associated with ordering constraints. In our approach, we reduce ODP to the Ordered simple path with mandatory nodes problem (OSPMN), i.e., the problem of finding a simple path containing a set of mandatory nodes in a given order. The reduction of the problem is motivated by the fact that we have an appropriate way of dealing with OSPMN based on DomReachability, a propagator that implements a generalized reachability constraint on a directed graph based on the concept of graph variables. The DomReachability constraint has three arguments: (1) a flow graph, i.e., a directed graph with a source node; (2) the dominance relation graph on nodes and edges of the flow graph; and (3) the transitive closure of the flow graph. Our experimental evaluation of DomReachability shows that it provides strong pruning, obtaining solutions with very little search. Furthermore, we show that DomReachability is also useful for defining a good labeling strategy. These experimental results give evidence that DomReachability is a useful primitive for solving constrained path problems over directed graphs.</div>
</front>
</TEI>
<affiliations><list><country><li>Belgique</li>
</country>
<region><li>Province du Brabant wallon</li>
<li>Région wallonne</li>
</region>
<settlement><li>Louvain-la-Neuve</li>
</settlement>
<orgName><li>Université catholique de Louvain</li>
</orgName>
</list>
<tree><country name="Belgique"><region name="Région wallonne"><name sortKey="Quesada, Luis" sort="Quesada, Luis" uniqKey="Quesada L" first="Luis" last="Quesada">Luis Quesada</name>
</region>
<name sortKey="Collet, Raphael" sort="Collet, Raphael" uniqKey="Collet R" first="Raphaël" last="Collet">Raphaël Collet</name>
<name sortKey="Collet, Raphael" sort="Collet, Raphael" uniqKey="Collet R" first="Raphaël" last="Collet">Raphaël Collet</name>
<name sortKey="Deville, Yves" sort="Deville, Yves" uniqKey="Deville Y" first="Yves" last="Deville">Yves Deville</name>
<name sortKey="Deville, Yves" sort="Deville, Yves" uniqKey="Deville Y" first="Yves" last="Deville">Yves Deville</name>
<name sortKey="Quesada, Luis" sort="Quesada, Luis" uniqKey="Quesada L" first="Luis" last="Quesada">Luis Quesada</name>
<name sortKey="Van Roy, Peter" sort="Van Roy, Peter" uniqKey="Van Roy P" first="Peter" last="Van Roy">Peter Van Roy</name>
<name sortKey="Van Roy, Peter" sort="Van Roy, Peter" uniqKey="Van Roy P" first="Peter" last="Van Roy">Peter Van Roy</name>
</country>
</tree>
</affiliations>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Musique/explor/MozartV1/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 001949 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 001949 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien |wiki= Wicri/Musique |area= MozartV1 |flux= Main |étape= Exploration |type= RBID |clé= ISTEX:2BD8576A6CA4FBEB76BD8024838A23403B19C579 |texte= Using Dominators for Solving Constrained Path Problems }}
This area was generated with Dilib version V0.6.20. |